#ifndef AVL_TREE_H
#define AVL_TREE_H

#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include <stdbool.h>
#include <stdint.h>


typedef struct _avl_tree_node {
    int data;
    struct _avl_tree_node *left;
    struct _avl_tree_node *right;
}avl_node;
typedef   avl_node * avl_tree;
enum {
    AVL_LLL_UB,
    AVL_LR_UB,
    AVL_RL_UB, 
    AVL_RRR_UB,
    AVL_NORMAL,
};

enum {
    AVL_TREE_LEFT_TREE,
    AVL_TREE_RIGHT_TREE,
};


bool avl_tree_delete( avl_tree *r, int data);

avl_tree avl_tree_lookup(avl_tree *r, int data);
avl_tree avl_tree_lookup_pa(avl_tree *r, avl_tree tag);


int avl_tree_get_height(avl_tree r);


int avl_tree_get_ub_type(avl_tree head_ub_node);
bool avl_tree_is_unbalanced_tree(avl_tree r);
uint32_t avl_tree_is_unbalanced_tree_imp(avl_tree r);
uint32_t avl_tree_get_head_unbalanced_node(avl_tree r, avl_node **p);
bool avl_tree_find(avl_tree *r, int  dt);

/*return root node of avl tree*/
avl_tree avl_tree_insert(avl_tree *r, int data);

void avl_tree_adjust(avl_tree *r);
/*avl delete all */
void avl_tree_free(avl_tree *r);

/* 
tree rebalanced
*/

/*rrr adjust*/
avl_tree avl_tree_RotateL( avl_tree head_ub_node );

/*lll adjust*/
avl_tree avl_tree_RotateR( avl_tree head_ub_node );

/*lr adjust*/
avl_tree avl_tree_RotateLR( avl_tree head_ub_node );

/*rl adjust*/
avl_tree avl_tree_RotateRL( avl_tree head_ub_node );


#endif